/**
 * 20. 有效的括号
 * https://leetcode-cn.com/problems/valid-parentheses/
 */
public class Solutions_20 {
    public static void main(String[] args) {
//        String str = "()";  // output: true
//        String str = "()[]{}";  // output: true
//        String str = "(]";  // output: false
//        String str = "([)]";  // output: false
        String str = "{[]}";  // output: true

        boolean result = isValid(str);
        System.out.println(result);
    }

    public static boolean isValid(String s) {
        int len = s.length();
        char[] stack = new char[len];
        int idx = 0;
        char[] arr = s.toCharArray();

        for (char c : arr) {
            // c 为开区间字符时，栈中存储闭区间字符
            if (c == '(') {
                stack[idx++] = ')';
            } else if (c == '[') {
                stack[idx++] = ']';
            } else if (c == '{') {
                stack[idx++] = '}';
            } else {
                // 遍历到闭区间字符时，如果没有开区间字符，或者栈顶的开区间字符不匹配，return false
                if (idx < 1 || stack[idx - 1] != c) {
                    return false;
                }
                idx--;
            }
        }
        // 若全部匹配，最终栈中为空
        return idx == 0;
    }
}
